﻿
/**
 * Search Interface
 */
public abstract class IGenericSearch
{
    /**
     * Problem description
     */
    UndirectedGraph mGraph;

    /**
     * Constructor
     */
    public IGenericSearch(string fn)
    {
        mGraph = new UndirectedGraph();
        mGraph.readInProblem(fn);
    }

    /**
     * Generic sceleton for search on the problem
     */
    public System.Collections.Generic.List<Node> genericGraphSearch(string initialState, string goalState)
    {
        /** setup graph for search */
        mGraph.setupProblem(initialState, goalState);

        /** fringe <- INSERT(MAKE_NODE(INITIAL-STATE[problem]), fringe) */
        generic_insertToFringe(mGraph.findNode(initialState));

        /** 
         * Loop do
         *  if EMPTY?(fringe) then return failure
         */
        while (!generic_isFringeEmpty()) {
            
            /** node <- REMOVE_FIRST(fringe) */
            Node node = generic_removeFirst();

            /**
             * if GOAL-TEST[[problem] applied to STATE[node] successds
             *  then return SOLUTION(node)
             */
            if (mGraph.isGoal(node)) { return constructPathByNode(node); }

            /**
             * fringe <- INSERT-ALL(EXPAND(node, problem), fringe)
             */
            generic_insertAll(generic_expand(node));

        }
        return null;
    }


    /**
     * Get Path by a node
     */
    public System.Collections.Generic.List<Node> constructPathByNode(Node node)
    {
        System.Collections.Generic.List<Node> result = new System.Collections.Generic.List<Node>();

        /** current node */
        Node current = node;        

        /** construct path */
        do {
            result.Add(current);
            current = current.getParent();
        } while (current != null);

        /** reverse order */
        result.Reverse();

        /** return constructed path */
        return result;
    }


    /**
     * expands a node and returns list of chosen new nodes
     */
    public System.Collections.Generic.List<Node> generic_expand(Node parent)
    {
        /** successors <- the empty set */
        System.Collections.Generic.List<Node> result = new System.Collections.Generic.List<Node>();

        /**
         * for each <action, result> in SUCCESSOR-FN[problem](STATE[node]) do
         *      s <- a new NODE
         *      STATE[s] <- result
         *      PARENT-NODE[s] <- node
         *      ACTION[s] <- action
         *      PATH-COST[s] <- PATH-COST[node] + STEP-COST(node, action, s)
         *      DEPTH[s] <- DEPTH[node] + 1
         *      add s to successors
         * return successors
         */
        foreach (System.Tuple<Edge, Node> tuple in mGraph.getSuccessors(parent)) {
            Edge edge = tuple.Item1;
            Node child = tuple.Item2;
            child.setParent(parent);
            child.setPredecessorEdge(edge);
            child.setPathCost(parent.getPathCost() + edge.getStepCost());
            child.setDepth(parent.getDepth() + 1);
            result.Add(child);
        }

        return result;
    }

    /** to implement by specific search strategy */

    /**
     * insert a node to the fringe 
     */
    public abstract void generic_insertToFringe(Node n);

    /**
     * test if fringy is empty
     */
    public abstract bool generic_isFringeEmpty();

    /**
     * remove first element of fringe 
     */
    public abstract Node generic_removeFirst();

    /**
     * insert nodes into fringe 
     */
    public abstract void generic_insertAll(System.Collections.Generic.List<Node> nodes);
}

